package huaweiod.first;

import java.util.HashMap;
import java.util.Map;

/**
 * 华为OD机试真题 Java 实现【最左侧冗余覆盖子串】【100%通过率】【2022.11 Q4 新题】
 * 滑动窗口不是很理解 new
 */
public class A_2023_28_MostLeftOverrideSubString {

    /**
     * 给定两个字符串 s1和 s2 和正整数k，其中 s1 长度为 n1，s2 长度为 n2, 在s2中选一个子串，满足
     * 1: 该子串长度为n1+k
     * 2: 该子串中包含s1中全部字母
     * 3: 该子串每个字母出现次数不小于s1中对应的字母, 我们称s2的长度k冗余覆盖s1,
     * 给定s1，s2，k,
     * 求最左侧的s2以长度k几余覆盖s1的子串的首个元素的下标如果没有返回-1。
     */
    public static int process(String s1, String s2, int k) {
        int n1 = s1.length();
        int n2 = s2.length();
        if (n1 + k > n2) {
            return -1;
        }
        // 统计次数
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s1.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        // s2子串 ：n1 + k
        int left = 0;
        while (left + n1 + k <= n2) {
            String sub = s2.substring(left, left + n1 + k);
            if (sub.contains(s1)) {
                Map<Character, Integer> subMap = new HashMap<>();
                for (char c : sub.toCharArray()) {
                    if (subMap.containsKey(c)) {
                        subMap.put(c, map.get(c) + 1);
                    } else {
                        subMap.put(c, 1);
                    }
                }
                boolean flag = true;
                for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                    if (!sub.contains(entry.getKey().toString()) && subMap.get(entry.getKey()) < entry.getValue()) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
            left++;
        }
        return left + n1 + k <= n2 ? left : -1;
    }

    public static void main(String[] args) {
        System.out.println(process("ab", "aabcd", 1));      // 0
        System.out.println(process("abc", "dfs", 10));      // -1
    }
}
